Share a simplified version of backtrack solution:

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        n = len(board)

        rows, cols, boxes = collections.defaultdict(set), collections.defaultdict(set), collections.defaultdict(set)

        for r in range(n):
            for c in range(n):
                if board[r][c] == '.':
                    continue

                v = int(board[r][c])
                rows[r].add(v)
                cols[c].add(v)
                boxes[(r // 3) * 3 + c // 3].add(v)


        def is_valid(r, c, v):
            box_id = (r // 3) * 3 + c // 3
            return v not in rows[r] and v not in cols[c] and v not in boxes[box_id]


        def backtrack(r, c):
            if r == n - 1 and c == n:
                return True
            elif c == n:
                c = 0
                r += 1

            # current grid has been filled
            if board[r][c] != '.':
                return backtrack(r, c + 1)

            box_id = (r // 3) * 3 + c // 3
            for v in range(1, n + 1):
                if not is_valid(r, c, v):
                    continue

                board[r][c] = str(v)
                rows[r].add(v)
                cols[c].add(v)
                boxes[box_id].add(v)

                if backtrack(r, c + 1):
                    return True

                # backtrack
                board[r][c] = '.'
                rows[r].remove(v)
                cols[c].remove(v)
                boxes[box_id].remove(v)

            return False


        backtrack(0, 0)

There's no need creating extra data structure as rows, columns and boxes. It's good for engineering, but not practical for interview. Here's a succint version of backtracing

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        # Check if num can be placed at board[i][j]
        def can_place(i, j, num):
            # Check row
            if any(num == n for n in board[i]):
                return False
            
            # Check col
            if any(num == n for n in list(zip(*board))[j]):
                return False
            
            # Check box
            start_row, start_col = (i // 3) * 3, (j // 3) * 3
            for r in range(start_row, start_row + 3):
                for c in range(start_col, start_col + 3):
                    if num == board[r][c]:
                        return False
            return True
        
        def find_unassigned():
            for r in range(len(board)):
                for c in range(len(board[0])):
                    if board[r][c] == '.':
                        return r, c
            return -1, -1
        
        def solve():
            r, c = find_unassigned()
            
            if r == -1 and c == -1:
                return True
            
            for num in [str(n) for n in range(1, 10)]:
                if can_place(r, c, num):
                    board[r][c] = num
                    if solve():
                        return True
                    board[r][c] = '.'
            return False
		
        if not board:
            return
        solve()

For simplicity during an interview

Time Complexity: O(9^(m * n))
Space Complexity: O(m*n)

i have three times faster java code(3 ms), what i do is first fill the cells which can only fill one number:

class Solution {
    // box size
    int n = 3;
    // row size
    int N = n * n;

    int [][] rows = new int[N][N + 1];
    int [][] columns = new int[N][N + 1];
    int [][] boxes = new int[N][N + 1];

    char[][] board;

    boolean sudokuSolved = false;

    public boolean couldPlace(int d, int row, int col) {
        /*
        Check if one could place a number d in (row, col) cell
        */
        int idx = (row / n ) * n + col / n;
        return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
    }

    public boolean couldPlaceOnlyOne( int row, int col) {
        /*
        Check if one could only place one number in (row, col) cell
        */
        int place = 0, count = 0;
        for (int d = 1; d < 10; d++) {
            int idx = (row / n ) * n + col / n;
            if (rows[row][d] + columns[col][d] + boxes[idx][d] == 0) {
                count += 1;
                place = d;
            }
        }
        if (count == 1) {
            placeNumber(place, row, col);
        }
        return false;
    }

    public void placeNumber(int d, int row, int col) {
        /*
        Place a number d in (row, col) cell
        */
        int idx = (row / n ) * n + col / n;

        rows[row][d]++;
        columns[col][d]++;
        boxes[idx][d]++;
        board[row][col] = (char)(d + '0');
    }

    public void removeNumber(int d, int row, int col) {
        /*
        Remove a number which didn't lead to a solution
        */
        int idx = (row / n ) * n + col / n;
        rows[row][d]--;
        columns[col][d]--;
        boxes[idx][d]--;
        board[row][col] = '.';
    }

    public void placeNextNumbers(int row, int col) {
        /*
        Call backtrack function in recursion
        to continue to place numbers
        till the moment we have a solution
        */
        // if we're in the last cell
        // that means we have the solution
        if ((col == N - 1) && (row == N - 1)) {
            sudokuSolved = true;
        }
        // if not yet
        else {
            // if we're in the end of the row
            // go to the next row
            if (col == N - 1) backtrack(row + 1, 0);
            // go to the next column
            else backtrack(row, col + 1);
        }
    }

    public void backtrack(int row, int col) {
        /*
        Backtracking
        */
        // if the cell is empty
        if (board[row][col] == '.') {
            // iterate over all numbers from 1 to 9
            for (int d = 1; d < 10; d++) {
                if (couldPlace(d, row, col)) {
                    placeNumber(d, row, col);
                    placeNextNumbers(row, col);
                    // if sudoku is solved, there is no need to backtrack
                    // since the single unique solution is promised
                    if (!sudokuSolved) removeNumber(d, row, col);
                }
            }
        } else placeNextNumbers(row, col);
    }

    public void solveSudoku(char[][] board) {
        this.board = board;

        // init rows, columns and boxes
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                char num = board[i][j];
                if (num != '.') {
                    int d = Character.getNumericValue(num);
                    placeNumber(d, i, j);
                }
            }
        }
        while (true) {
            int flag = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (board[i][j] == '.') {
                        if (couldPlaceOnlyOne(i, j) == true) {
                            flag = 1;
                        }
                    }
                }
            }
            if (flag == 0) {
                break;
            }

        }
        backtrack(0, 0);
    }
}

why this code only work in python 3 not 2?

I think the operations analysis is wrong. Even the second number has 8 possible candidates, you're still trying to fill from 1-9 for every position. You're not eliminating any number when trying to fill. So I'd say the operation should be 9 ^ (9 * 9)

Clean Python3, dfs by row-based.

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def is_block_valid(i: int, j: int) -> bool:
            nums = [board[r][c] for r in range(i-2, i+1) for c in range(j-2, j+1)]
            return len(nums) == len(set(nums))

        def dfs(i: int, j: int, row: set = None) -> bool:
            if i == 9: return True
            if j == 9: return dfs(i+1, 0)
            if i % 3 == 2 and j % 3 == 2 and not is_block_valid(i, j): return False
            if j == 0: row = {str(i) for i in range(1, 10)} - set(board[i])
            if board[i][j] != '.': return dfs(i, j+1, row)
            if row:
                for num in row & cols[j]:
                    board[i][j] = num
                    cols[j].discard(num)
                    row.discard(num)
                    if dfs(i, j+1, row): return True
                    cols[j].add(num)
                    row.add(num)
                board[i][j] = '.'
            return False

        used_cols = [set(row[j] for row in board) for j in range(9)]
        cols = [{str(i) for i in range(1, 10)} - nums for nums in used_cols]
        dfs(0, 0)

Why two functions are calling each other?

i have three times faster python code(80 ms), what i do is first fill the cells which can only fill one number:

from collections import defaultdict


class Solution:
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        def could_place(d, row, col):
            """
            Check if one could place a number d in (row, col) cell
            """
            return not (d in rows[row] or d in columns[col] or
                        d in boxes[box_index(row, col)])

        def place_number(d, row, col):
            """
            Place a number d in (row, col) cell
            """
            rows[row][d] += 1
            columns[col][d] += 1
            boxes[box_index(row, col)][d] += 1
            board[row][col] = str(d)

        def remove_number(d, row, col):
            """
            Remove a number which didn't lead 
            to a solution
            """
            del rows[row][d]
            del columns[col][d]
            del boxes[box_index(row, col)][d]
            board[row][col] = '.'

        def could_place_only_one(row, col):
            # if only a number can file in the cell, fill it.
            count = []
            for d in range(1, 10):
                if could_place(d, row, col):
                    count.append(d)
            if len(count) == 1:
                place_number(count[0], row, col)
                return True
            return False

        def firstcheck():
            while 1:
                flag = 0
                for i in range(N):
                    for j in range(N):
                        if board[i][j] == '.' and could_place_only_one(i, j) == True:
                            flag = 1
                if flag == 0:
                    break

        def place_next_numbers(row, col):
            """
            Call backtrack function in recursion
            to continue to place numbers
            till the moment we have a solution
            """
            # if we're in the last cell
            # that means we have the solution
            if col == N - 1 and row == N - 1:
                nonlocal sudoku_solved
                sudoku_solved = True
            # if not yet
            else:
                # if we're in the end of the row
                # go to the next row
                if col == N - 1:
                    backtrack(row + 1, 0)
                # go to the next column
                else:
                    backtrack(row, col + 1)

        def backtrack(row=0, col=0):
            """
            Backtracking
            """
            # if the cell is empty
            if board[row][col] == '.':
                # iterate over all numbers from 1 to 9
                for d in range(1, 10):
                    if could_place(d, row, col):
                        place_number(d, row, col)
                        place_next_numbers(row, col)
                        # if sudoku is solved, there is no need to backtrack
                        # since the single unique solution is promised
                        if not sudoku_solved:
                            remove_number(d, row, col)
            else:
                place_next_numbers(row, col)

        # box size
        n = 3
        # row size
        N = n * n
        # lambda function to compute box index

        def box_index(row, col): return (row // n) * n + col // n

        # init rows, columns and boxes
        rows = [defaultdict(int) for i in range(N)]
        columns = [defaultdict(int) for i in range(N)]
        boxes = [defaultdict(int) for i in range(N)]
        for i in range(N):
            for j in range(N):
                if board[i][j] != '.':
                    d = int(board[i][j])
                    place_number(d, i, j)

        sudoku_solved = False
        firstcheck()
        backtrack()

it also makes sense to precalculate the empty indexes and then using the index for backtracking and not to calculate the next empty index every time

def backtrack(curr_idx)
    if curr_idx == len(empty_spaces):
                return board
    curr_row, curr_col = empty_spaces[curr_idx]
    ....
    for digit in range(1, 10):
                board[curr_row][curr_col] = str(digit)
                if self.validate_move(board, curr_row, curr_col):
                    solved = backtrack(curr_idx + 1)
                    ....